//
// Created by xili on 2024/8/24 14:37.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        unordered_map<char, int> ump;
        for (auto &item: s1) {
            ump[item]++;
        }
        int n = s1.size();
        int m = s2.size();
        if (n > m) {
            return false;
        }
        int i = 0;
        for (; i < n && i < m; i++) {
            if (ump.count(s2[i])) {
                ump[s2[i]]--;
            }
        }
        if (ok(ump)) {
            return true;
        }
        for (; i < m; i++) {
            if (ump.count(s2[i])) {
                ump[s2[i]]--;
            }
            if (ump.count(s2[i - n])) {
                ump[s2[i - n]]++;
            }
            if (ok(ump)) {
                return true;
            }
        }
        return false;
    }

    bool ok(const unordered_map<char, int> &m) {
        for (auto &item: m) {
            if (item.second != 0) {
                return false;
            }
        }
        return true;
    }
};
